package com.it.zhangjun.arithmetic.栈;

import java.util.Stack;

/**
 * @author zhangj
 * @description 大鱼吃小鱼
 * @date 2021-03-18 19:53
 */
public class LT_大鱼吃小鱼 {
    public static void main(String[] args) {
        int[] size = {4, 2, 5, 3, 1};
        int[] direction = {1, 1, 0, 0, 0};
        System.out.println(solution(size, direction));
    }

    public static int solution(int[] fishSize, int[] fishDirection) {
        //拿到鱼的数量，如果数量小鱼等于1，直接返回鱼的数量
        int fishNum = fishSize.length;
        if (fishNum <= 1) {
            return fishNum;
        }
        //0表示鱼向左
        int left = 0;
        //1表示鱼向右
        int right = 1;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < fishNum; i++) {
            //当前鱼的情况
            int currentDirection = fishDirection[i];
            int currentSize = fishSize[i];
            //当前的鱼是否被栈中的鱼吃掉
            boolean hasEat = false;
            //  如果栈中还有鱼，并且栈中的鱼向右，当前的鱼向左，那么就有可能相遇
            while (!(stack.isEmpty()) && fishDirection[stack.peek()] == right &&
                    currentDirection == left) {
                //  如果栈顶的鱼比较大，那么把新来的吃掉
                if (fishSize[stack.peek()] > currentSize) {
                    hasEat = true;
                    break;
                }
                //如果栈中的鱼较小，那么会把栈中的鱼吃掉
                stack.pop();
            }
            //如果新来的鱼没有被吃掉，那么压栈
            if (!hasEat) {
                stack.push(i);
            }
        }
        return stack.size();
    }
}